#include <stdio.h>
#include <stdlib.h> 
#include <time.h>

/*
*  Função que troca valores de dois inteiros.
*   
*  entradas: unsigned int , unsigned int
*  saidas: void
*/
void swap(unsigned int *a, unsigned int *b) {
   unsigned int temp;
   temp = *b;
   *b = *a;
   *a = temp;   
}

/*
 * Função que verifica se a matriz T (aleatória) converge numa matriz ordenada
 * Consiste na analise de sequencias de numeros na matriz T.
 * O teste de convergencia é positivo quando na matriz existem
 * quatro posições seguidas com o mesmo valor. O facto de serem testadas quatro
 * posições tem a haver com o calculo de z1..z4 e a possibilidade de destes resultarem
 * em situações de excepção, como por exemplo:
 *    z1=9 z2=9 z3=9 z4=9  T[0]=9  T[999]=9  N=39321
 * 
 * Entradas: matriz T de 1000 posições
 * Saidas: inteiro (0-sem convergencia 1-convergente)
 */
int conv(unsigned int *T) {
    unsigned int i=0;
    int flag = 0;
    do {
	if ((T[i] == T[i+1])&&(T[i+1] == T[i+2])&&(T[i+2] == T[i+3])) 
		flag = 1;
	i++;
    } while ((i < 997)&&(flag ==0) );	
    return flag;
}

/*
*  Função que efectua o preenchimento de uma matriz
*  com valores aleatórios de 0 a 9. Esta função implementa
*  validação para que #{0} = #{1} = ... = #{9}.
* 
*  Entrada: array de 1000 posições
*  Saida: void
*/
void preencher_tabela(unsigned int *T) {
    unsigned int p, i, ncount[10]={0};
	i = 0;
	do {
			p = rand() % 10;
			if (ncount[p] < 100){    
				ncount[p]++;
				T[i] = p;
                i++;
			}
	} while (i < 1000);
}

/*
* Função que implemeta o algoritmo de geração de numeros pseudo-aleatórios
* apresentado no enunciado do trabalho proposto.
* 
* Entrada: array T de 1000 posições (num. aleatórios de 0 a 9) e tnum numeros aleatórios a gerar 
* Saida: p/consola dos numeros aleatórios gerados
*/
void rand2(unsigned int *T, unsigned int tnum) {
    unsigned int N, p, z1, z2, z3, z4, i,l;
	
    p = rand() % 1000;
	for (i = 0;i < tnum;i++) {		 //+600		

        /* verificação de convergencia na tabela T*/
        while (conv(T) != 0) preencher_tabela(T);
    
        if (p >= 1000) 
            p = 0;   // reset para posição 0 l=p=0

        l = p;
		swap(&T[l], &T[0]);
        z1 = T[0];              // equiv a z1=T[l] antes do swap
        l = (p < 999) ? (p + 1) : 0;
		swap(&T[l], &T[0]);
        z2 = T[0];
        l = (p < 998) ? (p + 2) : 0;
		swap(&T[l], &T[0]);
        z3 = T[0];	
        l = (p < 997) ? (p + 3) : 0;
		swap(&T[l], &T[0]);
        z4 = T[0];

		N = z1 << 12 | z2 << 8 | z3 << 4 | z4;		
        printf("%d\n",N);
		p = z1 * 100 + z2 * 10 + z3 * 1 + 1;
	}	
}

int main (void) {	
	unsigned int T[1000];
	
    /* incialização do gerador de numeros pseudo-aleatórios do C */
 	srand(time(NULL)); 

    /* preenchimento da tabela T com numero aleatórios de 0 a 9 */
    preencher_tabela(T);

    /* geração de numeros pseudo-aleatórios */
    rand2(T, 1000000);
	return 0;
}
